A typical network to which the invention applies comprises a large number of network nodes, e.g., work stations, organized in autonomous domains. Communications between bordering (logically) domains are, to some extent, organized by units such as routers that employ the Border Gateway Protocol. With this protocol a router communicates with a peer router in a neighboring domain by means of a connection such as TCP/IP to provide the latter router with the next-hop IP addresses of routers to which data intended for network nodes within the domain, or beyond, should be directed. The Border Gateway Protocol (BGP) is described in RFC 1771. Specifically, a BGP router advertises to its peers updates of the paths over which traffic should be directed to search particular nodes located within the domain or through the domain to another domain.
The present invention relates to the processing of “reachability events”, i.e., changes in the status of units within the domain that may affect paths advertised to the peers. For example, a “next-hop” node within the domain or another node further along the path to the recipient of messages may have failed or otherwise be unavailable; or if previously unavailable has become available. Notifications of many, if not most, of these events are ordinarily received in messages transmitted by other nodes in the domain. To provide certainty, the BGP unit might periodically scan all the next-hop units in the paths advertised by the unit to its peers. However the scanning interval then has to be unduly long to cope with churning.